package com.hy;

import java.util.HashMap;
import java.util.Map;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:频率跟踪器
 * <p>
 * 请你设计并实现一个能够对其中的值进行跟踪的数据结构，并支持对频率相关查询进行应答。
 *
 * 实现 FrequencyTracker 类：
 * FrequencyTracker()：使用一个空数组初始化 FrequencyTracker 对象。
 * void add(int number)：添加一个 number 到数据结构中。
 * void deleteOne(int number)：从数据结构中删除一个 number 。数据结构 可能不包含 number ，在这种情况下不删除任何内容。
 * bool hasFrequency(int frequency): 如果数据结构中存在出现 frequency 次的数字，则返回 true，否则返回 false。
 * 提示：
 * 1 <= number <= 105
 * 1 <= frequency <= 105
 * 最多调用 add、deleteOne 和 hasFrequency 共计 2 * 105 次
 *
 * User:Mr.Du
 * Date:2024/3/21
 * Time:10:03
 */

/**
 * 双哈希解决
 */
public class FrequencyTracker {

    Map<Integer, Integer> mp;
    Map<Integer, Integer> map;
    public FrequencyTracker() {
        mp = new HashMap<>();
        map = new HashMap<>();
    }

    public void add(int number) {
        int value = mp.getOrDefault(number, 0) + 1;
        mp.put(number, value);
        map.put(value, map.getOrDefault(value, 0) + 1);
        if(map.getOrDefault(value - 1, 0) > 0){
            map.put(value - 1, map.get(value - 1) - 1);
        }
    }

    public void deleteOne(int number) {
        int value = mp.getOrDefault(number, 0);
        if(value == 0) return;
        mp.put(number, value - 1);
        map.put(value, map.get(value) - 1);
        if(value > 1){
            map.put(value - 1, map.getOrDefault(value - 1, 0) + 1);
        }
    }

    public boolean hasFrequency(int frequency) {
        return map.getOrDefault(frequency, 0) > 0;
    }
}

/**
 * 数组解决
 */
class FrequencyTrackerUseArray {

    int n = 200000;
    int[] arr, nums;
    public FrequencyTrackerUseArray() {
        arr = new int[n];
        nums = new int[n];
    }

    public void add(int number) {
        int t = arr[number];
        arr[number]++;
        nums[t + 1]++;
        if(nums[t] > 0){
            nums[t]--;
        }
    }

    public void deleteOne(int number) {
        int t = arr[number];
        if(t == 0) return;
        arr[number]--;
        nums[t]--;
        if(t > 1) nums[t-1]++;

    }

    public boolean hasFrequency(int frequency) {
        return nums[frequency] > 0;
    }
}